/*
练习4.1 根据后序和中序遍历输出先序遍历 (25分)
time:20201217 10:09 AM
key:1.每一次递归分成三步 赋值 分别为左右子树在原数组上切片出合适的数组 如果数组不空 则递归本流程
user：ldc
*/

#include <iostream>
using namespace std;
#include<stack>
#include<algorithm>
#include<queue>
class Tree
{
public:
	int data;
	Tree* lchild;
	Tree* rchild;

	Tree()
	{
		data = -1;
		lchild = NULL;
		rchild = NULL;
	}
};
void read(Tree* node)
{
	if (node != NULL)
	{
		cout <<" "<<node->data;
		read(node->lchild);
		read(node->rchild);
	}
}
void creat(vector<int> last_array, vector<int> mid_array, Tree* head)
{
	
	//把后序遍历数组最后元素一个赋予本节点数据
	head->data = last_array[last_array.size() - 1];
	//返回距离，这个距离是中序遍历数组起点到在中序遍历数组中上面后序遍历数组最后一个元素的距离。
	int x=distance(begin(mid_array), find(begin(mid_array), end(mid_array), head->data));
	//为这个节点的左右节点准备后序与中序遍历数组。1左2右。
	vector<int> last_array1;
	vector<int> last_array2;
	vector<int> mid_array1;
	vector<int> mid_array2;
	//左边都好办，都是取到本次的前x个作为下一轮的后、中序遍历数组。
	for (int i = 0; i < x; i++)
	{
		last_array1.push_back(last_array[i]);
	}
	for (int i = 0; i < x; i++)
	{
		mid_array1.push_back(mid_array[i]);
	}
	//右边的后序就取，从x开始至本轮数组长度-1（后序中本轮数组长度-1位置的元素是本轮节点）。
	for (int i= x; i < last_array.size()-1 ; i++)
	{
		last_array2.push_back(last_array[i]);
	}
	//右边的中序就取，从x+1（中序中x位置的元素是本轮节点）开始至本轮数组长度。
	for (int i = x+1; i < last_array.size(); i++)
	{
		mid_array2.push_back(mid_array[i]);
	}
	//左右两边取得的新后序或者中序（等价）非空，则new对应子树，放入递归循环。
	if (!last_array1.empty())
	{
		head->lchild = new Tree;
		creat(last_array1, mid_array1, head->lchild);
	}
	if (!last_array2.empty())
	{
		head->rchild = new Tree;
		creat(last_array2, mid_array2, head->rchild);
	}
}
int main()
{
	Tree* head = new Tree;
	int i,n,x;
	
	cin >> n;
	vector<int> last_array;
	vector<int> mid_array;
	queue<int> sort_array;
	/*
	7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
	*/
	for (i = 0; i < n; i++)
	{
		cin >> x;
		last_array.push_back(x);
	}
	for (i = 0; i < n; i++)
	{
		cin >> x;
		mid_array.push_back(x);
	}
	//顺序取last末节点
	creat(last_array, mid_array, head);
	//按格式输出
	cout << "Preorder:";
	read(head);
}




